package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/binary-tree-level-order-traversal/">二叉树的层序遍历(Binary Tree Level Order Traversal)</a>
 * <p>给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [3,9,20,null,null,15,7]
 *      输出：[[3],[9,20],[15,7]]
 *
 * 示例 2：
 *      输入：root = [1]
 *      输出：[[1]]
 *
 * 示例 3：
 *      输入：root = []
 *      输出：[]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数目在范围 [0, 2000] 内</li>
 *     <li>-1000 <= Node.val <= 1000</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0102BinaryTreeLevelOrderTraversal_M 二叉树的层序遍历
 * @see LC0107BinaryTreeLevelOrderTraversal_II_M 二叉树的层序遍历II
 * @since 2023/5/11 10:42
 */
public class LC0102BinaryTreeLevelOrderTraversal_M {

    static class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> resList = new ArrayList<>();
            if (root == null) {
                return resList;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int currLevelNodeSize = queue.size();
                List<Integer> currLevelNodeValList = new ArrayList<>();
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode currNode = queue.poll();
                    currLevelNodeValList.add(currNode.val);
                    if (currNode.left != null) {
                        queue.offer(currNode.left);
                    }
                    if (currNode.right != null) {
                        queue.offer(currNode.right);
                    }
                }
                resList.add(currLevelNodeValList);
            }
            return resList;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        Solution solution = new Solution();

        Printer.printListListInteger(solution.levelOrder(root));
    }
}